// https://www.lintcode.com/problem/longest-increasing-subsequence/

public class Solution {
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        if (nums.length == 0) {
            return 0;
        }
        int ret = 0;
        int[] cache = new int[nums.length]; // 到当前位置最长子序列长度
        Arrays.fill(cache, 0);
        cache[0] = 1;
        for (int i = 1; i < nums.length; ++i) {
            int len = 0;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    len = Math.max(cache[j], len);
                }
            }
            cache[i] = len + 1;
            ret = Math.max(cache[i], ret);
        }
        return ret;
    }
}